1. Field of the Invention
This invention relates to the field of computer systems and, more particularly, to systems and methods of optimizing lock operations within computer systems.
2. Description of the Related Art
Computer systems can suffer severe performance degradation as a result of lock operations. In general, lock operations are associated with software locks which are used by computer systems to ensure that only one process at a time can access a resource, such as a critical region of memory. Throughout this specification, a memory region is used as an example of a resource associated with a lock. It is noted that the disclosed invention is equally applicable to other resources, such as an input/output location. A variety of locks have been implemented, ranging from simple spin-locks to advanced queue-based locks. Although simple spin-lock implementations can create very bursty traffic as described below, they are still the most commonly used software lock within computer systems.
Systems employing locks typically require that a given process perform an atomic operation to obtain access to a critical memory region. For example, an atomic test-and-set operation is commonly used. Generally speaking, an atomic operation is an indivisible operation. In other words, another process cannot access the lock between the test and set portion of the atomic operation. The test-and-set operation is performed to determine whether a lock bit associated with the memory region is cleared and to atomically set the lock bit. That is, the test allows the process to determine whether the memory region is free of a lock by another process, and the set operation allows the process to acquire the lock if the lock bit is cleared.
Referring now to FIG. 1, a diagram illustrating a spin-lock implementation is shown. In a spin-lock implementation, if the test of the lock bit indicates that the memory region is currently locked, i.e. another process has acquired the lock, the requesters for the lock initiate a loop wherein the lock bit is continuously read until the lock bit is cleared, at which time the process reinitiates the atomic test-and-set operation. Generally speaking, requesters are processes or other entities that seek to acquire the lock. Spin-locks may be implemented using either optimistic or pessimistic spin-lock algorithms. An optimistic spin-lock is depicted by the following algorithm:
For the optimistic spin-lock algorithm shown above, the process first performs an atomic test-and-set operation upon the lock bit corresponding to the memory region for which access is sought. If the atomic test-and-set operation fails, the process reads the lock bit in a repetitive fashion until the lock bit is cleared by another process. The process then reinitiates the atomic test-and-set operation. Generally speaking, a read-to-own (RTO) transactions requests write access to data and a read-to-share (RTS) transaction requests read access to data. It is noted that names other than RTO and RTS may be used to describe the concepts of acquiring read and write access to data.
A pessimistic spin-lock is depicted by the following algorithm:
For the pessimistic spin-lock algorithm, the process first reads the lock bit corresponding to the memory region for which access is sought in a repetitive fashion until the lock bit is cleared. When the process determines that the lock bit is clear in accordance with the read operation(s), the process performs an atomic test-and-set operation to lock and gain access to the memory region. If the test failed upon execution of the atomic test-and-set operation, the process again repetitively reads the lock bit until it is cleared.
In a shared memory computer system in which the requester performs a system bus, or global, transaction to test and set the lock, the above spin-lock algorithms create a large number of bus transactions. If the lock is not available, each requester attempting to acquire the lock bit continually performs global transactions until the lock becomes available. This large number of global transactions may adversely affect the performance of the computer system by using a large portion of the available bandwidth.
To reduce the number of global transactions performed by a spin-lock algorithm, the lock bit may be cached by each requester attempting to acquire it. In this manner, the repetitive reads to determine the state of the lock bit may be local transactions rather global transactions. While this may reduce the number of global transactions, the coherency traffic on the bus generated when the state of the lock bit changes may be unacceptable.
In a cached shared memory system, the read (or test) of the lock bit is treated as a read-to-share (RTS) operation. Since the atomic test-and-set operation includes a write, it is treated as a read-to-own (RTO) operation. The system will thus place the coherency unit containing the lock bit in a modified state in response to the atomic test-and-set operation.
For both the pessimistic and optimistic algorithms discussed above, when a memory region corresponding to a contended spin-lock is released, the owner writes to the lock to free it generating a RTO operation (1 bus transaction) which invalidates the line in the caches of all other devices. Therefore, all N spinning requesters subsequently miss and generate RTS transactions for the cache line containing the lock. The first requester to receive a data reply detects the free lock and generates an RTO transaction (1 bus transaction). Since the requester of each of the remaining RTS requests similarly receive an indication that the lock is free, each of these requesters also generates a RTO transaction (Nxe2x88x921 bus transactions). When the first RTO transaction is received, the requester issuing that transaction locks and gains access to the memory region. The test-and-set operations corresponding to the RTO requests of the remaining requesters therefore fail. The remaining Nxe2x88x922 requesters generate RTS transactions to cache the new lock bit (Nxe2x88x922 bus transactions).
Thus, the total number of transactions is potentially 3Nxe2x88x921 for the single transfer of a spin-lock from one requester to another (where N is the number of contenders for the lock). Due to this large number of transactions, the latency associated with the release of a lock until the next contender can acquire the lock is relatively high. The large number of transactions can further limit the maximum frequency at which ownership of the lock can migrate from node to node. Finally, since only one of the spinning requesters will achieve the lock, the failed test-and-set operations of the remaining processors result in undesirable RTO requests on the network. The coherency unit in which the lock is stored undesirably migrates from requester to requester, invalidating other copies. Network traffic is thereby further increased despite the fact that the lock is set.
Several lock designs to improve the performance of spin-locks have been devised, such as back-off locks and queue locks. In back-off locks, the requesters contending to acquire the lock implement a delay between attempts to acquire the lock. In this manner, the number of requesters contending for the lock at a given instance of time is reduced. The lock may be released and acquired by another requester before some requesters detect that the lock has been freed. Accordingly, the number of processes that attempt to acquire the lock when it becomes available is reduced. Low contention for the lock reduces the number of transactions when the lock changes state. The requesters that do not contend for the lock will generate a read-to-share transaction to read the new lock bit, but will not generate the read-to-share and read-to-own transactions to attempt to acquire the lock.
The delay implemented by a backup lock may be constant or variable. In a constant delay implementation, the requester delays a fixed time between attempted accesses to the lock. In a variable delay implementation, the duration of the delay may be different for different requesters. An exponential back-off lock is one example of variable delay back-off lock. In a exponential back-off lock, the delay implemented by the requester increases with each unsuccessful attempt to acquire the lock.
Back-off locks unfortunately may delay the acquisition of the lock. When a lock becomes available, a delay may occur before a process attempts to acquire the lock. This delay can increase the latency of a lock operation and reduce the performance of the computer system. Further, back-off locks can create fairness problems. Because each contending process has an equal chance of acquiring the lock, a process then has just begun waiting for the lock may be more likely to acquire the lock before a process that has been waiting for a long time. It is also theoretically possible for a waiting process to never acquire the lock.
Queue locks are another technique for reducing the overhead of lock operations. Referring now to FIG. 2, each requester for the lock is queued up behind earlier requesters. In.this manner, only the process at the head the queue attempts to acquire the lock when it becomes available and generates bus transactions. Queue locks have the added benefit that they may be more fair than spin-locks because the earlier processes get the lock before processes that enter the queue later.
Unfortunately, in practice, queue locks have several disadvantages. For example, queue locks require space proportional to the number of queued requesters instead of the constant space required by spin-locks. This may make queue locks incompatible with some synchronization library interfaces. Further, if the process at the head of the queue is suspended or currently not running, the other processes behind the suspended process may not be able to acquire the lock. Still further, queue locks may be less efficient then spin locks if there is no contention for lock. Overhead may be incurred to check the queue to verify that no requesters are waiting to acquire the lock.
The problems outlined above are in large part solved by a probabilistic queue lock in accordance with the present invention. The probabilistic queue lock is a hybrid of a queue lock and a back-off lock. The probabilistic queue lock divides requesters for the lock into at least three sets. In one embodiment, the requesters are divided into the owner of the lock, the first waiting contender, and the other waiting contenders. The first waiting contender is made probabilistically more likely to obtain the lock by having it spin faster than the other waiting contenders. Because the other waiting contenders spin more slowly, the first waiting contender is more likely to be able to observe the free lock and acquire it before the other waiting contenders notice that it is free. The first of the other waiting contenders that determines that the previous first waiting contender has acquired the lock is promoted to be the new first waiting contender and begins spinning fast. A lock in accordance with present invention advantageously eliminates the delay in acquiring the lock present in back-off lock implementations, and eliminates the suspended process problems and variable space required by queue locks. At the same time, a lock implementation in accordance with the present invention advantageously reduces the number of transactions required to acquire the lock. Because only the first waiting contender is spinning fast on the lock, it is probable that only the first waiting contender will attempt to acquire the lock when it becomes available.
Broadly speaking, the present invention contemplates a method of synchronizing access to a resource in a computer system that includes a lock corresponding to the resource and a plurality of requesters that may attempt to access the resource, wherein the lock has at least three lock states. The method includes: a first requester of the plurality of requesters requesting acquisition of the lock; if the lock is in a free state, the first requester setting the lock to a held state and acquiring the lock; if the lock is in the held state, the first requester setting the lock to a wait state and spinning fast; and if the lock is in the wait state, the first requester spinning slow.
The present invention further contemplates a computer-readable storage medium comprising program instructions for synchronizing access to a resource in a computer system that includes a lock corresponding to the resource and a plurality of requesters that may attempt to access the resource, wherein the lock has at least three lock states. The program instructions are operable to implement the steps of: a first requester of the plurality of requesters requesting acquisition of the lock; if the lock is in a free state, the first requester setting the lock to a held state and acquiring the lock; if the lock is in the held state, the first requester setting the lock to a wait state and spinning fast; and if the lock is in the wait state, the first requester spinning slow.
The present invention still further contemplates a method of synchronizing access to a resource in a computer system that includes a lock corresponding to the resource and a plurality of requesters that may attempt to access the resource, wherein the lock has at least four lock states. The method includes: a first requester of the plurality of requesters requesting acquisition of the lock; if the lock is in a free state, the first requester setting the lock to a first held state and acquiring the lock; if the lock is in the first held state, the first requester setting the lock to a second held state and spinning fast; if the lock is in the second held state, the first requester setting the lock to a wait state and spinning medium; and if the lock is in the wait state, the first requester spinning slow.